1710B - Rain - CodeForces Solution

class SegTree: 
    def __init__(self, a):
        self.n = len(a)
        self.t = [0]*(2*self.n)
        for i in range(self.n):
            self.t[self.n+i] = a[i]
        for i in range(self.n-1, 0, -1):
            self.t[i] = max(self.t[i << 1], self.t[(i << 1) | 1])
    
    def query(self, l, r):
                  ans = -1e9; l += self.n; r += self.n + 1
        while l<r:
            if (l & 1): ans = max(ans, self.t[l]); l += 1
            if (r & 1): r -= 1; ans = max(ans, self.t[r])
            l >>= 1; r >>= 1
        return ans

import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

t = int(input())
for tidx in range(t):
    n, m = [int(y) for y in input().split()]
    ex = [0]*n
    ep = [0]*n
    f = [0]*(3*n)
    d2 = dict()
    for i in range(n):
        x, p = [int(y) for y in input().split()]
        f[3*i] = x-p
        f[3*i+1] = x
        f[3*i+2] = x+p
        d2[x-p] = d2.get(x-p, 0) + 1
        d2[x] = d2.get(x, 0) - 2
        d2[x+p] = d2.get(x+p, 0) + 1
        ex[i] = x
        ep[i] = p
    f = list(set(f))
    l = len(f)
    f.sort()
    d = dict()
    for i in range(l):
        d[f[i]] = i
    q = [0]*(l)
    q3 = [0]*(l)
    q4 = [0]*(l)
    s = 0
    for i in range(l-1):
        s += d2[f[i]]
        q[i+1] = q[i] + s*(f[i+1]-f[i])
    q3 = [q[i] + n-f[i] for i in range(l)]
    q4 = [q[i] + f[i] for i in range(l)]
    
    m1 = [0]*l
    m2 = [0]*l
    m3 = SegTree(q3)
    m4 = SegTree(q4)
    m1[0] = q[0]
    for i in range(l-1):
        m1[i+1] = max(m1[i], q[i+1])
    m2[l-1] = q[l-1]
    for i in range(l-1, 0, -1):
        m2[i-1] = max(m2[i], q[i-1])
        
    ans = ["0"]*n
    for i in range(n):
        x = ex[i]
        p = ep[i]
        g = max(m1[d[x-p]], m2[d[x+p]], m3.query(d[x-p], d[x]) - (n-x) - p, m4.query(d[x], d[x+p]) - x - p)
        if g <= m: ans[i] = "1"
    print("".join(ans))